/*
 * @lc app=leetcode.cn id=933 lang=java
 *
 * [933] 最近的请求次数
 */

// @lc code=start
class RecentCounter {

    DeQueue counter;

    public RecentCounter() {
        counter = new DeQueue();
    }
    
    public int ping(int t) {

        counter.pushBack(t);
        // int pre3000 = 0;
        while(t - counter.getFront() > 3000){
            counter.popFront();
        }
        return counter.count;
    }


    //双端队列
    class DeQueue{
        ListNode head;//虚头结点
        ListNode tail;//虚尾结点
        int count = 0;
        DeQueue(){
            head = new ListNode();
            tail = new ListNode();

            head.next = tail;
            tail.pre = head;
        }
        public void pushBack(int val){
            tail.insertPre(new ListNode(val));
            count ++;
        }
        public void pushFront(int val){
            head.inserNext(new ListNode(val));
            count ++;
        }
        public int popBack(){
            if(isEmpty()) return -1;
            int poped = tail.pre.val;
            tail.deletePre();
            count --;
            return poped;
        }
        public int popFront(){
            if(isEmpty()) return -1;
            int poped = head.next.val;
            head.deleteNext();
            count --;
            return poped;
        }
        public int getBack(){
            if(isEmpty()) return -1;
            int poped = tail.pre.val;
            return poped;
        }
        public int getFront(){
            if(isEmpty()) return -1;
            int poped = head.next.val;
            return poped;
        }
        public boolean isEmpty(){
            return head.next == tail;
        }
    }


    //双向链表节点
    class ListNode{
        int val;
        ListNode next;
        ListNode pre;

        public ListNode(){}
        public ListNode(int val){
            this.val = val;
        }
        public void inserNext(ListNode node){
            //将node放进去
            node.pre = this;
            node.next = this.next;

            //整理node相邻的两个节点
            //下面现行的顺序不能换，换了，this.next.pre的指向就不一样了
            if(null != this.next) this.next.pre = node;
            this.next = node;
        }
        public void insertPre(ListNode node){
            //将node放进去
            node.pre = this.pre;
            node.next = this;

            //整理node相邻的两个节点
            //下面现行的顺序不能换，换了，this.pre.next的指向就不一样了
            if(null!=this.pre) this.pre.next = node;
            this.pre = node;
        }
        public void deleteNext(){
            if(null == this.next) return ;

            if(null!=this.next.next) this.next.next.pre = this;
            this.next = this.next.next;
        }
        public void deletePre(){
            if(null == this.pre) return;

            if(null != this.pre.pre) this.pre.pre.next = this;
            this.pre = this.pre.pre;
        }
    }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */
// @lc code=end

